package 二叉树;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class No437路径总和III {

    /**
     * 给定一个二叉树，它的每个结点都存放着一个整数值。
     *
     * 找出路径和等于给定数值的路径总数。
     *
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     *
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     *
     * 示例：
     *
     * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     *
     *       10
     *      /  \
     *     5   -3
     *    / \    \
     *   3   2   11
     *  / \   \
     * 3  -2   1
     *
     * 返回 3。和等于 8 的路径有:
     *
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3.  -3 -> 11
     */

    int count;

    //双重递归写法 O(n^2)
    public int pathSum(TreeNode root, int sum) {
        if(root==null)
            return 0;
        checkOk(root,sum);
        pathSum(root.right,sum);
        pathSum(root.left,sum);
        return count;
    }
    //递归单一节点
    private void checkOk(TreeNode node,int number){
        /**
         * 个人习惯了写void,然后将变量提在外面,那样更好理解递归
         */
        if(node==null)
            return;
        number-=node.val;
        if(number==0){
            //符合条件的一个
            count++;
        }
        checkOk(node.left,number);
        checkOk(node.right,number);
    }

    private int count2;

    /**
     * 利用前缀和的思想,时间复杂度为O(n),保存遍历此条树下所有路径之和
     * 再利用减法机制去判断 目标节点到此节点的距离是否为target
     */
    public int pathSumGood(TreeNode root,int sum){
        /**
         * 此Map只会存储当前节点及其子节点的(遍历到现在的和)
         * k->前缀和 v->前缀和为此的个数
         */
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);//前缀和为0的个数为1
        /**
         * 前缀和的思想
         */
        dg(root,sum,0,map);
        return count2;
    }

    private void dg(TreeNode node,int target,int sum,Map<Integer,Integer> map){
        if(node==null)
            return;
        sum+=node.val;//获得当前节点的前缀和
        //获取差值,有的话,就是目标节点到此节点的路径之和为target
        count2+=map.getOrDefault(sum-target,0);
        map.put(sum,map.getOrDefault(sum,0)+1);
        dg(node.left,target,sum,map);
        dg(node.right,target,sum,map);
        //后面会遍历到别的树上去,记得取出
        map.put(sum,map.get(sum)-1);
    }


}
